/*
    Flood is a program to test the cut method on soft constraints problems
    Copyright (C) 2011  Mattia Gamba

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/


#include "solver.h"

Solver::Solver()
{
}

Solution Solver::solveProblem(Problem * pr){

    bool solution = true;
    QVector<int> ins_sol(pr->_pam.getN());
    QVector<int> previous_solution;
    jumps.clear();
    int previous_cut = -1;
    int cuts_done = 0;
    int alpha = 0;
    //Cuts
    QDateTime start = QDateTime::currentDateTime();
    while(solution){
        QCoreApplication::processEvents();
        //Save last working parameters
        previous_cut = alpha;
        previous_solution = ins_sol;
        //find minimum cut
        alpha = findMinimum(previous_cut, pr);
        //generates an hard problem using the cut found before
        Problem * pTest = pr->getCutHard(alpha);
        //is this cut valid?
        solution = solveHard(pTest, ins_sol);
        delete pTest;

        cuts_done++;
    }
    QDateTime end = QDateTime::currentDateTime();
    float jumps_avg = 0;
    for(int i = 0; i < jumps.size(); i++){
        jumps_avg += jumps[i];
    }
    jumps_avg /= jumps.size();
    return Solution(start.msecsTo(end),pr->_pam, previous_solution, previous_cut, jumps_avg, cuts_done);

}

int Solver::findMinimum(int prev, Problem * pm){
    int minFound = 10;
    QMap<QPair<int,int>, Link>::const_iterator it = pm->constraints.begin();
    while (it != pm->constraints.end()) {
        QMap<int,uint>::const_iterator lb = (*it).floats.lowerBound(prev + 1);
        if( lb.key() < minFound )
            minFound = lb.key();
        ++it;
    }
    for(int i = 0; i < pm->variables.size(); i++){
        QMap<int,uint>::const_iterator lb = pm->variables[i].floats.lowerBound(prev + 1);
        if( lb.key() < minFound )
            minFound = lb.key();
    }
    return minFound;
}

bool Solver::solveHard(Problem * pr, QVector<int>& solution){

    this->pr = pr;
    this->jumpz = 0;
    bool success = false;
    if(checking){

        bool failure = false;
        solution.fill(-1);
        prop(-1, 0, pr->variables, failure);
        if(!failure){
            solveWithProp(0,pr->variables,success,solution);
        }


    }
    else{
        QVector<int> instantiation(pr->_pam.getN(),-1);
        solveNoProp(0,pr->variables,success,solution);
    }
    jumps.push_back(jumpz);
            return success;

}

/*
 Recursive backtracking search with constraint propagation
 */

void Solver::solveWithProp(int j, QVector<Variable> va, bool& success, QVector<int>& instantiation ){

    while (!va[j].vals.isEmpty() && !success){
        QVector<Variable> inner(va);
        int d = va[j].vals.constBegin().key();
        va[j].vals.remove(d);
        if( cons(instantiation, j, d)){
            instantiation[j] = d;
            success = (j == instantiation.size()-1);
            if (!success){
                bool failure = false;
                prop(j, d, inner, failure);
                if(!failure){
                    solveWithProp(j+1, inner, success, instantiation);
                    if(!success)
                        jumpz++;
                }
            }
        }
    }
}

/*
 Recursive backtracking search without constraint propagation
 */

void Solver::solveNoProp(int j, QVector<Variable> va, bool& success, QVector<int>& instantiation ){

    while (!va[j].vals.isEmpty() && !success){
        QVector<Variable> inner(va);
        int d = va[j].vals.constBegin().key();
        va[j].vals.remove(d);
        if( cons(instantiation, j, d)){
            instantiation[j] = d;
            success = (j == instantiation.size()-1);
            if (!success){
                solveNoProp(j+1, inner, success, instantiation);
                if(!success)
                    jumpz++;
            }
        }
    }
}

/*
 Constraints propagation
 */

void Solver::prop(int j, int d, QVector<Variable>& va, bool& failure){

    if(j == -1){
        j = 0;
        for(int i = 0; i < va.size(); i++){
            QMap<int,int> copy(va[i].vals);
            QMap<int,int>::const_iterator it = copy.constBegin();
            while(it != copy.constEnd()){
                if(it.value() == 0){
                    va[i].vals.remove(it.key());
                }
                ++it;
            }
            if(va[j].vals.isEmpty()){
                failure = true;
                return;
            }
        }
    }
    else{
        for(int k = j+1; k < va.size(); k++){
            QMap<int,int> copy(va[k].vals);
            QMap<int,int>::const_iterator it = copy.constBegin();
            while(it != copy.constEnd()){
                int check = pr->constraints.value(qMakePair(j,k)).constraint_table.value(qMakePair(d,it.key()));
                if(check == 0){
                    va[k].vals.remove(it.key());
                }
                ++it;
            }
            if(va[k].vals.isEmpty()){
                failure = true;
                return;
            }
        }
    }
}

/*
 Consistency check
 */

bool Solver::cons(QVector<int>& instantiation, int j, int d){

    if(pr->variables.at(j).vals.value(d) == 0)
        return false;
    int check = 0;
    for(int i = 0; i < j; i++){
        int sxdx = pr->constraints.value(qMakePair(i,j)).constraint_table.value(qMakePair(instantiation[i],d));
        if(sxdx == 10)
            check++;
    }
    if (check == j)
        return true;
    else
        return false;
}


